// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-26 20:30
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

import java.util.*;

public class LevelOrderBottom {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 实现二叉树的层次遍历

        // 两个队列交替使用
        Queue<TreeNode> p = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        p.offer(root);
        while (!p.isEmpty() || !q.isEmpty()) {
            ArrayList<Integer> ql = new ArrayList<>();
            ArrayList<Integer> pl = new ArrayList<>();
            while (!p.isEmpty()) {
                TreeNode t = p.poll();
                if (t.left != null) {
                    q.offer(t.left);
                }
                if (t.right != null) {
                    q.offer(t.right);
                }
                pl.add(t.val);
            }
            if (!pl.isEmpty()) {
                res.add(pl);
            }
            while (!q.isEmpty()) {
                TreeNode qt = q.poll();
                if (qt.left != null) {
                    p.offer(qt.left);
                }
                if (qt.right != null) {
                    p.offer(qt.right);
                }
                ql.add(qt.val);
            }
            if (!ql.isEmpty()) {
                res.add(ql);
            }
        }
        // 使用栈实现对res中的列表进行逆向存储
        Collections.reverse(res);
        return res;
    }
}

